package primary.code06_graph;

import java.util.*;

/**
 * 从某一点出发，到其他节点
 *
 * Dijkstra 算法算是贪心思想实现的，首先把起点到所有点的距离存下来找个最短的，然后松弛一次再找出最短的；
 * 所谓的松弛操作就是，遍历一遍看通过刚刚找到的距离最短的点作为中转站会不会更近，如果更近了就更新距离，这样把所有的点找遍之后就存下了起点到其他所有点的最短距离。
 *
 * 初始化到达某点的最短距离映射
 * 初始化最短距离待确认点集
 * while 存在待确认最短距离的点
 *      待确认点集中移除距离最小的点
 *      已该点为跳板，更新其他待确认点集的最短距离映射
 * end
 */
public class Code07_Dijkstra {

    public static HashMap<Node, Integer> dijkstra(Node from) {
        if (from == null) return null;
        //from 到 key 的距离为  value
        HashMap<Node, Integer> resMap = new HashMap<>();
        //已经确定最小距离的点
        HashSet<Node> certainedNode = new HashSet<>();
        resMap.put(from, 0);
        //找到一个距离距离最短，并且没有被确定的节点
        Node minNode = getMinDistanceNodeAndUncertained(resMap, certainedNode);
        while (minNode != null) {
            certainedNode.add(minNode);
            //找到所有可以到达的节点
            final List<Edge> edges = minNode.edges;
            for (Edge edge : edges) {
                Integer oldDistance = resMap.containsKey(edge.to) ? resMap.get(edge.to) : Integer.MAX_VALUE;
                Integer newDistance = edge.weight + resMap.get(minNode);
                if (newDistance < oldDistance) {
                    resMap.put(edge.to, newDistance);
                }
            }
            minNode = getMinDistanceNodeAndUncertained(resMap, certainedNode);
        }
        return resMap;
    }

    public static Map<Node, Integer> dijkstraTest(Node from) {
        Map<Node, Integer> nodeDistanceMap = new HashMap<>();
        Set<Node> uncertainNodeSet = new HashSet<>();
        Set<Node> certainNodeSet = new HashSet<>();

        nodeDistanceMap.put(from, 0);
        certainNodeSet.add(from);
        for (Edge edge : from.edges) {
            uncertainNodeSet.add(edge.to);
            nodeDistanceMap.put(edge.to, edge.weight);
        }

        while (!uncertainNodeSet.isEmpty()) {
            int minUncertainNodeDistance = Integer.MAX_VALUE;
            Node minUncertainNode = null;
            for (Node node : uncertainNodeSet) {
                if (nodeDistanceMap.get(node) < minUncertainNodeDistance) {
                    minUncertainNodeDistance = nodeDistanceMap.get(node);
                    minUncertainNode = node;
                }
            }
            uncertainNodeSet.remove(minUncertainNode);
            certainNodeSet.add(minUncertainNode);
            for (Edge edge : minUncertainNode.edges) {
                Node to = edge.to;
                if (!certainNodeSet.contains(to)) {
                    int oldDistance = nodeDistanceMap.get(to) == null ? Integer.MAX_VALUE : nodeDistanceMap.get(to);
                    int newDistance = minUncertainNodeDistance + edge.weight;
                    if (newDistance < oldDistance) {
                        nodeDistanceMap.put(to, newDistance);
                    }
                }
            }
        }
        return nodeDistanceMap;
    }


    /**
     * 找到一个距离距离最短，并且没有被确定的节点
     * @param resMap 从from到某节点的距离集合
     * @param certainedNode 被确定节点的集合
     * @return
     */
    private static Node getMinDistanceNodeAndUncertained(HashMap<Node, Integer> resMap, HashSet<Node> certainedNode) {
        Node res = null;
        Integer minDistance = Integer.MIN_VALUE;
        //此处遍历的方式可以优化为堆
        for (Map.Entry<Node, Integer> nodeDistance : resMap.entrySet()) {
            if (!certainedNode.contains(nodeDistance.getKey())) {
                if (res == null) {
                    res = nodeDistance.getKey();
                    minDistance = nodeDistance.getValue();
                } else {
                    res = nodeDistance.getValue() < minDistance ? nodeDistance.getKey() : res;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[][] arr = {
                {25, 1, 2},
                {25, 2, 1},

                {2, 1, 3},
                {2, 3, 1},

                {7, 1, 4},
                {7, 4, 1},

                {16, 2, 3},
                {16, 3, 2},

                {20, 2, 4},
                {20, 4, 2},

                {11, 4, 3},
                {11, 3, 4}
        };
        Graph graph = GraphUtils.transferGraph(arr);
        for (Map.Entry<Node, Integer> nodeIntegerEntry : dijkstra(graph.nodes.get(1)).entrySet()) {
            System.out.println(nodeIntegerEntry.getKey().val + "    " + nodeIntegerEntry.getValue());
        }
        System.out.println("===================");
        for (Map.Entry<Node, Integer> nodeIntegerEntry : dijkstraTest(graph.nodes.get(1)).entrySet()) {
            System.out.println(nodeIntegerEntry.getKey().val + "    " + nodeIntegerEntry.getValue());
        }

    }
}
